[luogu 2756]飞行员配对方案问题

本题链接:[luogu 2756]飞行员配对方案问题
题目大意:一共有$n$个飞行员,其中前$m$个是外籍飞行员,另外的都是本国飞行员.外籍飞行员编号为$1$到$m$,本国的为$m+1$到$n$.给定若干个关系表示某个外籍飞行员可以与本国飞行员配合.每架飞机需要一个外籍飞行员和一个本国飞行员一起操作,并且两人要能配合.问一次能派出多少个飞机.并输出每架飞机上两个飞行员的编号.

数据范围:
$1 \leq m \leq n \leq 100$

显然这是一个二分图求最大匹配,还要求一个具体方案.显然匈牙利算法可以做这个问题,不过这里给出用网络流的方式解决的做法:
①建图
对于一个二分图问题来说,建立一个超级原点$S$联通所有的外籍飞行员,在建一个超级汇点$T$联通所有的本国飞行员,对于每个关系,联通一个外籍飞行员和一个本国飞行员,三种边的流量都是$1$.最终二分图最大匹配数等价于在这张新图上的最大流.即从$S$流出了多少个边.
②具体方案
对于每条边而言,我们以正向边表示本来的题目里给出的关系,反向边表示残量网络里的反边.如果一个边被选上了,那么正向边流量会变成$0$,对应的反向边流量为$1$,遍历每个正向边,以异或$1$得到他对应的反向边(顺序存储特性),如果反向边流量为$1$说明这对关系被选上了,不过还要特别判断一下两边的点是否是$S$或者$T$,在这种情况下并不合法.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 205,M = 5005 * 2,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,d[N],pre[N];
ll incf[N],maxflow;
queue<int> q;
void add(int u,int v,int w)
{
	edge[++idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx; 
	
	edge[++idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx;
}
bool bfs()
{
	memset(d,0,sizeof d);
	while(q.size())	q.pop();
	q.push(s);d[s] = 1;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = ver[u];i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q.push(v);
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int flow)
{
	if(u == t)	return flow;
	int rest = flow,k,i;
	for(int i = ver[u];i && rest;i = succ[i])
	{
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(rest,cap[i]));
			if(!k)	d[v] = 0;
			cap[i] -= k;
			cap[i ^ 1] += k;
			rest -= k;
		}
	}
	return flow - rest;
}
int main()
{
	scanf("%d%d",&m,&n);
	int u,v;
	s = 0,t = n + 1;
	while((scanf("%d%d",&u,&v)) == 2)
	{
		if(u == -1 && v == -1)	break;
		add(u,v,1);
	}
	for(int i = 1;i <= m;++i)	add(s,i,1);
	for(int i = m + 1;i <= n;++i)	add(i,t,1);	
	int flow = 0;
	while(bfs())
		while(flow = dinic(s,INF))
			maxflow += flow;
	if(maxflow == 0)	puts("NO Solution.");
	else
	{
		printf("%lld\n",maxflow);
		for(int i = 2;i <= idx;i += 2)
		{
			int u = edge[i],v = edge[i ^ 1];
			if(u != s && v != s && u != t && v != t)
				if(cap[i ^ 1])
					printf("%d %d\n",v,u);
		}
	}	
    return 0;
}